Descrição
Server: 142.93.113.55
Port: 31086
Solução
Análise Inicial
A descrição do problema apenas nos fornece um endereço e porta para conectarmos. Usando o netcat
, temos a seguinte resposta.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
locutor@kali:~/Documents/fireshell/gamod$ nc 142.93.113.55 31086
+++ Fireshell CTF - GAMOD +++
[+] This is a MODified version of Guess the Number game.
[+] In this game the computer chooses a number X and you will have N chances to
discover the number.
[+] In each chance you will be able to ask a question (query) or answer the
correct number (only once). To ask a question you need to use 'q A B' where
A and B are two integers and the computer will return:
1 if (A MOD X) >= (B MOD X)
0 if (A MOD X) < (B MOD X)
[+] To answer the correct number uses 'a V' where V is the answer.
[+] Type 'start' to start:
|
O problema nos pede para encontrar um número X dentro de um intervalo dado, com o auxílio de uma operação que compara os módulos de dois números A e B.
$$1 \enspace\text{se } A \pmod X \geq B \pmod X$$
$$0 \enspace\text{se } A \pmod X \lt B \pmod X$$
Os primeiros rounds (de um total de 10) até são possíveis de resolver manualmente, mas logo o intervalo cresce muito e surge a necessidade de automatizarmos o processo.
Para resolver isto, precisamos descobrir como utilizar o algoritmo de busca binária
com a operação que ele nos dá. Então, poderemos escrever um código que encontre o número correto de maneira automatizada.
Escrevendo a solução
Uma vez que tive um norte, comecei a escrever a conexão com o servidor em python, utilizando a biblioteca de sockets.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
#!/usr/bin/python3
import sys
import socket
if __name__ == '__main__':
# Setup
host = "142.93.113.55"
port = 31086
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect((host, port))
sock.recv(8192).decode().strip()
sock.send('start'.encode())
time.sleep(1.5)
|
Esse código abre a conexão e envia o comando para iniciar o desafio (‘start’). Em seguida, precisei ler o retorno do servidor e parsear as informações relevantes.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
res = sock.recv(1024).decode().strip()
# Get range
rng = res[res.find('between'):]
rng = rng[rng.find('[')+1:rng.find(']')].split(',')
min = int(rng[0].strip())
max = int(rng[1].strip())
# Get chances
chances = int(res[res.find("with"):].split()[1])
print("=" * 10)
print("Round: " + str(round+1))
print("Range: [" + str(min) + ", " + str(max) + "]")
print("Chances: " + str(chances))
|
Com os dados armazenados em minhas variáveis, resta fazer o algoritmo da busca.
Resolvendo para um caso pequeno
Vamos resolver para o caso X=13 e intervalo [2,20], como exemplo.
Se eu comparar A=2 e B=4, recebo 0 como retorno, pois X é maior que ambos os números e, portanto, a comparação entre seus restos é a mesma que a comparação entre eles mesmos. O mesmo acontece se eu comparar A=4 e B=8.
Agora quando comparo A=8 e B=16, temos o retorno 1. Isto acontece porque X é maior que A mas menor que B, e quando aplicamos a operação A deixa a si mesmo como resto e B deixa resto 3, menor que 8. Isto é, descobrimos que X está no intervalo [8, 16].
Reduzindo o tamanho do intervalo, comparo A=8 e B=12. Com o retorno 0, sei que X não está nesse intervalo, e portanto se encontra em [12, 16].
Reduzo novamente o tamanho do intervalo, e comparo A=12 e B=14. Note que agora recebo 1, e sei portanto que X=13 ou X=14, pois é a única maneira do resto de A ser maior que o resto de B.
Finalmente, comparo A=12 e B=13, e o 1 como retorno me garante que X=13.
Perceba que esta foi uma maneira efetiva de encontrar X, reduzindo o tamanho do intervalo em que ele se encontra até conseguir isolá-lo. Note também que não corremos o risco de receber um falso-positivo ao testar um intervalo grande, pois todos os intervalos menores já haviam sido testados.
Resolvendo para o caso geral
Vamos simplesmente expandir o algoritmo utilizado para um caso geral, usando a mesma lógica apresentada acima. O código, em python, fica assim
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
# Initial values
win = 2 #- Window size
inf = 2 #- Inferior limit
sup = inf + win #- Superior limit
near = False #- Whether the first interval has been found.
for chance in range(chances):
# Print status
print("[Q("+str(chance+1)+"/"+str(chances)+")] "+str(inf)+" "+str(sup)+": ", end='')
# Send query
sock.send(('q ' + str(inf) +' '+ str(sup)).encode())
time.sleep(1.5)
# Receive response
res = sock.recv(1024).decode().strip()
# Parse response
aux = res.split('\n')[0]
ans = int(aux[len(aux)-1])
print(ans)
if win == 1 and ans == 1:
print("[A] "+str(sup))
sock.send(("a "+str(sup)).encode())
time.sleep(1.5)
break
if win == 1 and ans == 0:
print("[A] "+str(sup+1))
sock.send(("a "+str(sup+1)).encode())
time.sleep(1.5)
break
elif ans == 0 and not near:
win = win * 2
inf = sup
sup = inf + win
if sup > max:
sup = max
elif ans == 0 and near:
win = int(win/2)
inf = sup
sup = inf + win
elif ans == 1:
near = True
win = int(win / 2)
sup = inf + win
|
Usando essa solução para os 10 rounds, recebemos a flag:
F#{c00l-b1n4ry-se4rcH-W1TH-M0DuL0}
O código completo da solução se encontra a seguir.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
#!/usr/bin/python3
import sys
import socket
import time
def solve_round(round, sock):
res = sock.recv(1024).decode().strip()
# Get range
rng = res[res.find('between'):]
rng = rng[rng.find('[')+1:rng.find(']')].split(',')
min = int(rng[0].strip())
max = int(rng[1].strip())
# Get chances
chances = int(res[res.find("with"):].split()[1])
print("=" * 10)
print("Round: " + str(round+1))
print("Range: [" + str(min) + ", " + str(max) + "]")
print("Chances: " + str(chances))
# Initial values
win = 2
inf = 2
sup = inf + win
near = False
for chance in range(chances):
print("[Q("+str(chance+1)+"/"+str(chances)+")] "+str(inf)+" "+str(sup)+": ", end='')
sock.send(('q ' + str(inf) +' '+ str(sup)).encode())
time.sleep(1.5)
res = sock.recv(1024).decode().strip()
try:
aux = res.split('\n')[0]
ans = int(aux[len(aux)-1])
print(ans)
if win == 1 and ans == 1:
print("[A] "+str(sup))
sock.send(("a "+str(sup)).encode())
time.sleep(1.5)
break
if win == 1 and ans == 0:
print("[A] "+str(sup+1))
sock.send(("a "+str(sup+1)).encode())
time.sleep(1.5)
break
elif ans == 0 and not near:
win = win * 2
inf = sup
sup = inf + win
if sup > max:
sup = max
elif ans == 0 and near:
win = int(win/2)
inf = sup
sup = inf + win
elif ans == 1:
near = True
win = int(win / 2)
sup = inf + win
except:
print("\n[!] " + res)
break
if __name__ == '__main__':
# Setup
host = "142.93.113.55"
port = 31086
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect((host, port))
sock.recv(8192).decode().strip()
sock.send('start'.encode())
time.sleep(1.5)
for round in range(10):
solve_round(round, sock)
res = sock.recv(8192).decode().strip()
print(res)
print("Connection closed.")
sock.close()
|